//给你两棵二叉树： root1 和 root2 。 
//
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠
//，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。 
//
// 返回合并后的二叉树。 
//
// 注意: 合并过程必须从两个树的根节点开始。 
//
// 
//
// 示例 1： 
// 
// 
//输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
//输出：[3,4,5,5,4,null,7]
// 
//
// 示例 2： 
//
// 
//输入：root1 = [1], root2 = [1,2]
//输出：[2,2]
// 
//
// 
//
// 提示： 
//
// 
// 两棵树中的节点数目在范围 [0, 2000] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1261 👎 0


package LeetCode.editor.cn;

import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2023-08-14 01:03:10
 * @description 617.合并二叉树
 */
public class MergeTwoBinaryTrees {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new MergeTwoBinaryTrees().new Solution();

    }

    //力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
// Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /*dfs  时间空间，O（min(m,n))*/
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null) {
                return root2;
            }
            if (root2 == null) {
                return root1;
            }
            TreeNode node = new TreeNode(root1.val + root2.val);
            node.left = mergeTrees(root1.left, root2.left);
            node.right = mergeTrees(root1.right, root2.right);
            return node;
        }

        /*bfs*/
        public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
//如果 t1和t2中，只要有一个是null，函数就直接返回
            if (root1 == null || root2 == null) {
                return root1 == null ? root2 : root1;
            }
            LinkedList<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root1);
            q.add(root2);
            while (!q.isEmpty()) {
                TreeNode r1 = q.remove();
                TreeNode r2 = q.remove();
                r1.val += r2.val;
                //如果两者左子树都不为空就放入队列
                //如果r1的左为空，就r2挂到r1左子树上
                if (r1.left != null && r2.left != null) {
                    q.add(r1.left);
                    q.add(r2.left);
                } else if (r1.left == null) {
                    r1.left = r2.left;
                }
                //右子树同理
                if (r1.right != null && r2.right != null) {
                    q.add(r1.right);
                    q.add(r2.right);
                } else if (r1.right == null) {
                    r1.right = r2.right;
                }

            }
            return root1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
